package ljl.codetop;

import java.util.HashMap;
import java.util.Map;

/**
 * 可以说是常看常新，每次做都跟新题一样，从来就没会过
 */
public class _72_ed {

    static class tryout {
        /**
         * 加一个减一个改一个
         * dp[i - 1][j] 是加一个
         * dp[i][j - 1] 是减一个
         * dp[i - 1][j - 1] 是改一个
         * 一开始，0 开头的都是 i
         *
         * 居然蒙了个大差不差？我日？
         */
        public int minDistance(String word1, String word2) {
            int l1 = word1.length(), l2 = word2.length();
            int[][] dp = new int[l1 + 1][l2 + 1];
            for (int i = 0; i <= l2; i++) {
                dp[0][i] = i;
            }
            for (int i = 0; i <= l1; i++) {
                dp[i][0] = i;
            }
            for (int i = 1; i <= l1; i++) {
                for (int j = 1; j <= l2; j++) {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1))
                        dp[i][j] = dp[i - 1][j - 1];
                    else
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }

            return dp[l1][l2];
        }
    }

    /**
     * 逼友称之为【自顶向下方法】，提供了一种新思路
     * 这种解法不加缓存的的话根本没法用，重复计算太多了
     * 加了缓存还行
     */
    static class biyou {
        Map<String, Integer> cache = new HashMap<>();
        char[] buf1, buf2;
        public int minDistance(String word1, String word2) {
            buf1 = word1.toCharArray();
            buf2 = word2.toCharArray();
            return cached(0, 0);
        }
        int cached(int i, int j) {
            String key = i+","+j;
            if (cache.containsKey(key)) return cache.get(key);
            int res = topdown(i, j);
            cache.put(key, res);
            return res;
        }
        int topdown(int i, int j) {
            if (i == buf1.length) return buf2.length - j;
            if (j == buf2.length) return buf1.length - i;
            if (buf1[i] == buf2[j]) return cached(i + 1, j + 1);
            int add = cached(i + 1, j);
            int sub = cached(i, j + 1);
            int mod = cached(i + 1, j + 1);
            return Math.min(mod, Math.min(sub, add)) + 1;
        }
    }
}
